//322 Coin Change
/*
给定一些硬币的面额，求最少可以用多少颗硬币组成给定的金额

输入输出样例
	输入一个一维整数数组，表示硬币的面额；以及一个整数，表示给定的金额。输出一个整数，
	表示满足条件的最少的硬币数量。若不存在解，则返回-1

Input: coins = [1, 2, 5], amount = 11
Output: 3

在这个样例中，最少的组合方法是 11 = 5 + 5 + 1
*/
int coinChange(vector<int> &coins, int amount)
{
	if (coins.empty())
		return -1;
	vector<int> dp(amount + 1, amount + 2);
	dp[0] = 0;
	for (int i = 1; i <= amount; ++i)
	{
		for (const int &coin : coins)
		{
			if (i >= coin)
			{
				dp[i] = min(dp[i], dp[i - coin] + 1);
			}
		}
	}
	return dp[amount] == amount + 2 ? -1 : dp[amount];
}
